package baseclass.j_dp.dp.oneZeroBag;

import java.util.Arrays;

/**
 * 给定两个数组w和v， 两个数组长度相等， w[i]表示第i件商品的重量， v[i]表示第i件商品的价值。
 * 再给定一个整数bag， 要求你挑选商品的重量加起来一定不能超过bag，
 * 返回满足这个条件下， 你能获得的最大价值。
 *
 * @date 2020/3/2 12:19
 */
public class Code01_01Bag2 {
    public static int maxValue1(int[] W, int[] V, int i, int hasWeight, int bag) {
        //剩余容量
        if (hasWeight <= 0) return hasWeight == 0 ? 0 : Integer.MIN_VALUE;
        if (i >= W.length) {
            return 0;
        }
        return Math.max(
                maxValue1(W, V, i + 1, hasWeight, bag),
                maxValue1(W, V, i + 1, hasWeight - W[i], bag) + V[i]
        );
    }

    /**
     * 方式2：带有记忆性回溯。memo[i][j]表示来到i位置当前背包容量为j时，
     * 所能获得的最大利润。
     */
    public static int maxValue2(int[] W, int[] V, int bag) {
        int[][] memo = new int[W.length][bag + 1];
        for (int i = 0; i < W.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        return process(W, V, 0, bag, bag, memo);
    }

    private static int process(int[] W, int[] V, int i, int hasWeight, int bag, int[][] memo) {
//剩余容量
        if (hasWeight <= 0) return hasWeight == 0 ? 0 : Integer.MIN_VALUE;
        if (i >= W.length) {
            return 0;
        }

        if (memo[i][hasWeight] != -1) return memo[i][hasWeight];
        return memo[i][hasWeight] =
                Math.max(
                        process(W, V, i + 1, hasWeight, bag, memo),
                        process(W, V, i + 1, hasWeight - W[i], bag, memo) + V[i]
                );
    }

    /**
     * 方式3：DP1
     * dp[i][j]:表示决策完第i件商品后，背包容量为j时最大利润
     */
    public static int maxValue3(int[] W, int[] V, int bag) {
        int[][] dp = new int[W.length][bag + 1];
        //dp[0][j]表示决策第0号商品
        for (int j = 0; j <= bag; j++) {
            //只有第0号商品质量小于背包容量，才能装进去
            if (W[0] <= j) dp[0][j] = V[0];
        }
        //dp[i][0]全为0，表示背包质量为0
        for (int i = 1; i < W.length; i++) {
            for (int j = 0; j <= bag; j++) {
                //i物品不要
                dp[i][j] = dp[i - 1][j];
                //第i件物品要导致当前背包质量为j,那么对于i-1要有足够的空间。
                if (j - W[i] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], V[i] + dp[i - 1][j - W[i]]);
                }
            }
        }
        return dp[W.length - 1][bag];
    }

    /**
     * DP1优化空间。O(2n)
     */
    public static int maxValue4(int[] W, int[] V, int bag) {
        int[][] dp = new int[2][bag + 1];
        int temp = 0;
        for (int j = 0; j <= bag; j++) {
            if (j >= W[0]) dp[temp][j] = V[0];
        }
        for (int i = 1; i <= W.length - 1; i++) {
            for (int j = 0; j <= bag; j++) {
                //i物品不要
                dp[1 - temp][j] = dp[temp][j];
                //第i件物品要
                if (j - W[i] >= 0) {
                    dp[1 - temp][j] = Math.max(dp[1 - temp][j], V[i] + dp[temp][j - W[i]]);
                }
            }
            temp = 1 - temp;// 0 - 1 - 0 - 1
        }
        return dp[temp][bag];
    }

    /**
     * DP2优化空间。O(n)
     */
    public static int maxValue5(int[] W, int[] V, int bag) {
        int[] dp = new int[bag + 1];
        for (int j = 0; j <= bag; j++) {
            if (j >= W[0]) dp[j] = V[0];
        }
        for (int i = 1; i <= W.length - 1; i++) {
            //注意一定要从后往前遍历。
            // 这样才能保证更新的位置j 依赖的是原来的位置 j-W[i] (上次更新得商品)
            // 如果从前往后遍历，就是完全背包了。
            // 更新得位置j依赖当前的商品 j-W[i] 本次已经更新
           /* for (int j = bag; j >= 0; j--) {
                if (j - W[i] >= 0) {
                    dp[j] = Math.max(dp[j], V[i] + dp[j - W[i]]);
                }
            }*/
            //上面代码等价于
            for (int j = bag; j >= W[i]; j--) {
                dp[j] = Math.max(dp[j], V[i] + dp[j - W[i]]);
            }
        }
        return dp[bag];
    }

    public static void main(String[] args) {
        int[] weight = {3, 2, 4, 7};
        int[] value = {5, 6, 3, 19};
        int bag = 12;
        System.out.println(maxValue1(weight, value, 0, bag, bag));
        System.out.println(maxValue2(weight, value, bag));
        System.out.println(maxValue3(weight, value, bag));
        System.out.println(maxValue4(weight, value, bag));
    }
}
